package Lee_code;

import java.util.Arrays;

public class Lee_416_2 {
    public boolean canPartition(int[] nums) {
        int len = nums.length;
        int sum = Arrays.stream(nums).sum();
        int res = sum / 2;
        int[] dp = new int[res+1];
        if (sum%2 == 1)
            return false;
        // 化作背包问题, 背包能不能装下res个, 能不能装满, 重量和价值绑定
        for (int i=0; i<len; i++){
            for (int j=res; j>=nums[i]; j--){
                dp[j] = Math.max(dp[j-1], dp[j-nums[i]]+nums[i]);
            }
        }
        return dp[res] == res;
    }
}
